
import java.util.concurrent.atomic.AtomicReference;

public class LFQueue implements Queue {

	public class Node {
		public int value;
		public AtomicReference<Node> next;
		public Node (int val) {
			value = val;
			next = new AtomicReference<Node>(null);                   
		}		
	}

	protected AtomicReference<Node> head, tail;
	
	public LFQueue(){
		Node sentinel = new Node(-1);
		head = new AtomicReference<Node>(sentinel);
		tail = new AtomicReference<Node>(sentinel);
	}
	
	@Override
	public int deq(int tid) throws Exception {
		int data = -1;
		Node h, t, next;
		while (true){
			h = head.get();
			if (head.get()!= h)
				continue;
			t = tail.get();
			next = h.next.get();
			if (head.get() != h)
				continue;
			if (next==null)
				break;
			if (h==t){
				tail.compareAndSet(t, next);
				continue;
			}
			if (head.compareAndSet(h,next)){
				data = next.value;
				break;
			}
		}
		return data;
	}

	@Override
	public void enq(int tid, int value) {
		Node newNode = new Node(value);
		Node t, next;
		while (true){
			t = tail.get();
			next = t.next.get();
			if (tail.get() != t)
				continue;
			if (next != null){
				tail.compareAndSet(t, next);
				continue;
			}
			if (tail.get().next.compareAndSet(null, newNode))
				break;
		}
		tail.compareAndSet(t, newNode);
	}
}
